class Solution 
{
public:
	ListNode* partition(ListNode* head, int x)
	{
		ListNode* small = new ListNode(0);
		ListNode* smallHead = small;

		ListNode* large = new ListNode(0);
		ListNode* largeHead = large;

		while (head != nullptr)
		{
			if (head->val < x)
			{
				small->next = head;
				small = small->next;
			}
			else
			{
				large->next = head;
				large = large->next;
			}
			head = head->next;
		}
		small->next = largeHead->next;
		return smallHead->next;
		
	}
};